package com.yulongtian.offers.day202211.day20221105;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * https://leetcode.cn/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/comments/
 * 可
 * <p>
 * 判断合不合法，用个栈试一试:
 * 把压栈的元素按顺序压入，当栈顶元素和出栈的第一个元素相同，
 * 则将该元素弹出，出栈列表指针后移并继续判断。
 * 最后判断出栈列表指针是否指向出栈列表的末尾即可
 *
 * @author yulongTian
 * @create 2022-11-05 19:20
 */
public class Test01 {
    public static void main(String[] args) {
        int[] pushed = {2, 1, 0};
        int[] popped = {1, 2, 0};
        System.out.println(validateStackSequences(pushed, popped));
    }

    public static boolean validateStackSequences(int[] pushed, int[] popped) {
        int pushed_len = pushed.length;
        int popped_len = popped.length;
        if (pushed_len == 0 && popped_len == 0) {
            return true;
        }

        if (pushed_len == 1 && popped_len == 1) {
            return pushed[0] == popped[0];
        }

        Deque<Integer> stack = new ArrayDeque<>();

        int pushed_index = 0;
        int popped_index = 0;
        while (popped_index < popped_len) {
            if (stack.isEmpty()) {
                stack.push(pushed[pushed_index++]);
                if (!stack.isEmpty() && stack.peek() == popped[popped_index]) {
                    popped_index++;
                    stack.pop();
                }
                continue;
            }

            if (pushed_index < pushed_len) {
                stack.push(pushed[pushed_index++]);
            }
            while (true) {
                if (!stack.isEmpty() && stack.peek() == popped[popped_index]) {
                    popped_index++;
                    stack.pop();
                } else {
                    break;
                }
            }

            if (pushed_index == pushed_len && !stack.isEmpty() && stack.peek() != popped[popped_index]) {
                return false;
            }

        }

        return popped_index == popped_len;
    }

}
